package binaryTree;

import java.util.ArrayList;

public class Class230 {

    ArrayList<Integer> list;
    public int kthSmallest(TreeNode root, int k) {
        if (root==null){
            return 0;
        }
        list=new ArrayList<Integer>();
        traverse(root);
        int size = list.size();
        if (k>size||k<0){
            return 0;
        }else {
            return list.get(k-1);
        }
    }

    public  void  traverse(TreeNode root){
        if (root==null){
            return;
        }
        traverse(root.left);
        list.add(root.val);
        traverse(root.right);
    }


    /**
     * 下面是更高效的写法
    *
    * */


    int kthSmallest1(TreeNode root, int k) {
        // 利用 BST 的中序遍历特性
        traverse1(root, k);
        return res;
    }

    // 记录结果
    int res = 0;
    // 记录当前元素的排名
    int rank = 0;
    void traverse1(TreeNode root, int k) {
        if (root == null) {
            return;
        }
        traverse1(root.left, k);
        /* 中序遍历代码位置 */
        rank++;
        if (k == rank) {
            // 找到第 k 小的元素
            res = root.val;
            return;
        }
        /*****************/
        traverse1(root.right, k);
    }



}

